package com.zx._12_算法.排序;

import com.zx._12_算法.Arrs.IAS;
import com.zx._12_算法.Nums;


/**
 * @version v1.0
 * @Project: knowledge
 * @Title: Sort5  堆排序
 * @Description: 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序
 *         https://mp.weixin.qq.com/s/K3Q06HYHiIwqfMOOL2NBEA
 *
 *         时间复杂度：O(n*logn)
 * @author: zhangxue
 * @date: 2020年2月11日下午4:10:15
 * @company: 未知
 * @Copyright: Copyright (c) 2015
 */
public class Sort5_堆排序 implements IAS {

    /**
     * @param nums
     * @param i 非叶子节点
     * @param len
     */
    private static void adjustHeap(int[] nums, int i, int len) {
        int temp = nums[i];
        for (int k = 2 * i + 1; k < len; k = 2 * k + 1) {
            int left = k;
            int right = k + 1;

            // 1.比较左右叶子节点，k=最大的叶子节点
            if (right < len && nums[right] > nums[left]) {
                k = right;
            }
            // 2.比较最大的叶子节点与非叶子节点
            if (temp < nums[k]) {
                nums[i] = nums[k];
                nums[k] = temp;
                i = k;
            } else {
                break;
            }
        }
    }

    @Override
    public void sort(int[] nums) {
            /*
        已知2个公式：
        1. 某一个非叶子节点在数组中的位置是 k, 则这个节点的左节点=2*k+1, 右节点=2*k+2
        2. 最后一片叶子的父节点的索引= 数组长度/2 - 1
    */
        // 1.构建大顶堆
        for (int i = nums.length / 2 - 1; i >= 0; i--) {
            // 从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(nums, i, nums.length);
        }

        // 2.调整堆结构+交换堆顶元素与末尾元素
        for (int j = nums.length - 1; j > 0; j--) {
            Nums.swap(nums, 0, j);// 将堆顶元素与末尾元素进行交换
            adjustHeap(nums, 0, j);// 重新对堆进行调整
        }
    }
}
